package com.yt.ds.chapter4;

/**
 * @Author: lzf
 * @Date: 2020/7/27 17:17
 * @Description: 深度优先搜索
 */
public class DepthFirstSearch implements Search {
    private boolean[] marked;   // 是否访问过
    private int count;      // 与起点联通的顶点数

    public DepthFirstSearch(Graph graph, int s) {
        marked = new boolean[graph.getVertexNum()];
        dfs(graph, s);
    }

    /**
     * 描述：深度优先搜索  1.将访问的点设置为以访问  2.递归访问所有没有被标记过的邻居顶点
     * @param graph 图
     * @param v 顶点
     * @return "void"
     * @date: 2020/7/27 17:45
     */
    private void dfs(Graph graph, int v) {
        marked[v] = true;
        count++;
        for (int w : graph.adj(v)) {
            if(!marked[w]){
                dfs(graph,w);
            }
        }
    }

    @Override
    public boolean marked(int v) {
        return marked[v];
    }

    @Override
    public int count() {
        return count;
    }
}
